/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-15
 * Time: 8:55
 */
import java.util.*;
//
//class LRUCache {
//    //创建链表的节点
//    class Node{
//        //存储对应的key和val
//        public int val;
//        private int key;
//        private Node next;//存储下一个节点的地址
//        private Node prev;//存储上一个节点的地址
//
//        public Node(){}
//        public Node(int key,int val){
//            this.key = key;
//            this.val = val;
//        }
//
//    }
//    //一个哈希表用来查找双向链表
//    public Map<Integer,Node> map = new HashMap<Integer,Node>();
//    public int size;
//    public int capacity;
//    public Node head,tail;
//    public LRUCache(int capacity) {
//        int size =0;//数据有效个数
//        this.capacity = capacity;
//        head = new Node(0,0);
//        tail = new Node(0,0);
//        head .next =tail;
//        tail.prev = head;
//    }
//
//    public int get(int key) {
//        Node node = map.get(key);
//        if(node==null){
//            //key不存在
//            return -1;
//        }
//        //key存在的情况,将这个结点移动到头部,返回其对应的val值
//        moveToHead(node);
//        return node.val;
//    }
//
//    public void put(int key, int value) {
//        //put的时候要先看一看这个key存不存在
//        //key不存在,我们要创建一个节点,放到头部同时保存到map里还要检查增容情况
//        Node node = map.get(key);
//        if(node==null){
//            Node ListNode = new Node(key,value);
//            addTohead(ListNode);
//            map.put(key,ListNode);
//            this.size++;
//            if(this.size>this.capacity){
//                Node noderes = moveTail();
//                map.remove(noderes.key);
//                this.size--;
//            }
//        }else {
//            //修改对应的value
//            node.val = value;
//            moveToHead(node);
//        }
//    }
//
//    private Node moveTail(){
//        Node res = tail.prev;
//        removeNode(res);
//        return res;
//    }
//
//    private void moveToHead(Node node){
//        //先将这个节点在链表中删除,然后在将其放到头部
//        removeNode(node);
//        addTohead(node);
//    }
//
//    private void addTohead(Node node){
//        node.prev = head;
//        node.next = head.next;
//        head.next.prev = node;
//        head.next = node;
//    }
//
//    private void removeNode(Node node){
//        node.prev.next = node.next;
//        node.next.prev = node.prev;
//    }
//}

//
//class LRUCache1 {
//    class DLinkedNode {
//        int key;
//        int value;
//        DLinkedNode prev;
//        DLinkedNode next;
//        public DLinkedNode() {}
//        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
//    }
//
//    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
//    private int size;//LRU数据有效的个数
//    private int capacity;//LRU的总容量
//    private DLinkedNode head, tail;//双向链表的头尾结点
//
//    public LRUCache(int capacity) {//用来初始化LRU
//        this.size = 0;//有效个数为0
//        this.capacity = capacity;//初始化容量
//        // 使用伪头部和伪尾部节点
//        head = new DLinkedNode();
//        tail = new DLinkedNode();
//        //刚开始头尾结点连接在一起
//        head.next = tail;
//        tail.prev = head;
//    }
//
//    public int get(int key) {
//        DLinkedNode node = cache.get(key);//从哈希表中获取val->node
//        if (node == null) {//如果key不存在则返回-1
//            return -1;
//        }
//        // 如果 key 存在，先通过哈希表定位，再移到头部
//        moveToHead(node);
//        return node.value;//最后在返回值
//    }
//
//    public void put(int key, int value) {
//        //1.看这个key是否存在
//        // 如果不存在那么创建一个结点,将它放到头部,同时也要将它放在哈希表中保存,同时要检查容量
//        //如果key存在,那么将这个结点的value修改,将它移动到头部
//        DLinkedNode node = cache.get(key);//利用node保存key对应的节点
//        if (node == null) {//如果节点为null证明key不存在将它放在第一个位置,并且判断容量
//            // 如果 key 不存在，创建一个新的节点
//            DLinkedNode newNode = new DLinkedNode(key, value);
//            // 添加进哈希表
//            cache.put(key, newNode);
//            // 添加至双向链表的头部
//            addToHead(newNode);
//            ++size;
//            if (size > capacity) {
//                // 如果超出容量，删除双向链表的尾部节点
//                DLinkedNode tail = removeTail();
//                // 删除哈希表中对应的项
//                cache.remove(tail.key);
//                --size;
//            }
//        }
//        else {
//            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
//            node.value = value;
//            moveToHead(node);
//        }
//    }
//
//    private void addToHead(DLinkedNode node) {
//        node.prev = head;
//        node.next = head.next;
//        head.next.prev = node;
//        head.next = node;
//    }
//
//    private void removeNode(DLinkedNode node) {
//        node.prev.next = node.next;
//        node.next.prev = node.prev;
//    }
//    //将结点移动到头部 -> 删除这个结点,在头插到头部
//    private void moveToHead(DLinkedNode node) {
//        //把这个节点放在第一个位置就相当于将这个结点删除,然后在头插,就放到了第一个位置
//        //
//        removeNode(node);
//        addToHead(node);
//    }
//
//    private DLinkedNode removeTail() {//删除尾巴结点同时也要返回对应的值
//        DLinkedNode res = tail.prev;
//        removeNode(res);
//        return res;
//    }
//}


import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
class ListNode {
  int val;
  ListNode next = null;
  public ListNode(int val) {
    this.val = val;
  }
 }
class Solution {

    public ListNode reverseList(ListNode head) {
        if(head==null) return head;
        ListNode cur = head;
        ListNode prev = null;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode prev = dummyHead;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                prev.next = l1;
                l1 = l1.next;
            }else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        if(l1!=null){
            prev.next = l1;
        }else if(l2!=null){
            prev.next = l2;
        }
        return dummyHead.next;
    }
    public ListNode sortLinkedList (ListNode head) {
        //先按照奇偶将链表连接起来
        ListNode odd = new ListNode(-1);//奇
        ListNode even = new ListNode(-1);//偶
        ListNode cur = head;
        ListNode oddCur = odd;
        ListNode evenCur = even;
        while(cur!=null){
            oddCur.next = cur;
            oddCur = oddCur.next;
            cur = cur.next;
            evenCur.next = cur;
            evenCur = evenCur.next;
            if(cur!=null)
                cur = cur.next;
        }
        oddCur.next = even.next;
        ListNode fast = odd.next;
        ListNode slow = odd.next;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode newList = slow.next;
        slow.next = null;
        //开始反转这个链表newList
        ListNode newHead2 = reverseList(newList);
        return mergeTwoLists(odd.next,newHead2);
    }
}

public class TestDemo {

    public static void main(String[] args) {
         ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next =node6;
        Solution solution = new Solution();
        solution.sortLinkedList(node1);
    }

}
